#include <sstream>
#include <regex>

class Expression;
class BinaryExpression;
class Variable;
class Number;

class Expression {
	Expression *value;
	static const string is_paren, is_number, is_binary_operator, is_variable;
	static const tr1::regex isParen, isBinaryOperator, isNumber, isVariable, isToken;
	static Expression* parse(string s);
	static Expression* parseTokens(const tr1::sregex_token_iterator start, int length);
protected:
	virtual ostream& printToStream(ostream& o) { return (value) ? (o << *value) : o; }
	Expression(Expression* e):value(e) {;;;}
public:
	Expression(string s=""):value(Expression::parse(s)) { ;;; }
	//lower precedence gets done first
	virtual unsigned int getPrecedence() {
		if(value)
			return value->getPrecedence();
		return 0; 
	}
	~Expression() {
		if(this->value)
			delete this->value;
	}
	// only have to define this one because they all call printToStream()
	friend ostream& operator<<(ostream& out, Expression& e);
};

const string Expression::is_paren("[()]");								const tr1::regex Expression::isParen(is_paren);
const string Expression::is_number("\\d*\\.?\\d+");						const tr1::regex Expression::isNumber(is_number);
const string Expression::is_binary_operator("[\\\\/\\^\\*\\+\\-%]");	const tr1::regex Expression::isBinaryOperator(is_binary_operator);
const string Expression::is_variable("[_a-zA-Z][0-9_a-zA-Z]*");			const tr1::regex Expression::isVariable(is_variable);
	
const tr1::regex Expression::isToken(Expression::is_paren		    + "|" + Expression::is_number + "|" + 
									 Expression::is_binary_operator + "|" + Expression::is_variable);

class BinaryExpression: public Expression {
	string _op;
	Expression *left, *right;
protected:
	virtual ostream& printToStream(ostream& o) { 
		if(left != NULL && right != NULL) {
			//cout << left->getPrecedence() << right->getPrecedence() << getPrecedence() << endl;
			if(left->getPrecedence() > getPrecedence())
				o << '(' << (*left) << ')';
			else
				o << (*left);
			o << op();
			if(right->getPrecedence() > getPrecedence())
				o << '(' << (*right) << ')';
			else
				o << (*right);
		}
		return o;
	}
public:
	BinaryExpression(string op, Expression *left=NULL, Expression *right=NULL): Expression(""), _op(op), left(left), right(right) {;;;}
	string op() {return _op;}
	virtual unsigned int getPrecedence() {
		if(_op == "+" || _op == "-")
			return 4;
		else if(_op == "*" || _op == "/")
			return 3;
		else if(_op == "^")
			return 2;
		else if(_op == "%")
			return 1;
	}
	virtual void setLeft(Expression* l) {
		if(left)
			delete left;
		left = l;
	}
	virtual void setRight(Expression* r) {
		if(right)
			delete right;
		right = r;
	}
	~BinaryExpression() {
		if(left)	delete left;
		if(right)	delete right;
	}
};

class Variable: public Expression {
	string name;
	float value;
	bool hasValue;
protected:
	virtual ostream& printToStream(ostream& o) { return o << name; }
public:
	Variable(string name):name(name), value(0), hasValue(false) {;;;}
};

class Number: public Expression {
	float value;
protected:
	virtual ostream& printToStream(ostream& o) { return o << value; }
public:
	Number(float f = 0):value(f) {;;;}
};

Expression* Expression::parse(string s) {
	if(s.length() == 0)
		return NULL;
	
	tr1::sregex_token_iterator start(s.begin(), s.end(), Expression::isToken);
	const tr1::sregex_token_iterator end;
	return Expression::parseTokens(start, INT_MAX);
}
Expression* Expression::parseTokens(const tr1::sregex_token_iterator start, int length) {
	const tr1::sregex_token_iterator end;
	Expression* prev = NULL;
	/*cout << '"';
	int p = 0;
	for(tr1::sregex_token_iterator i(start); i != end && p < length; ++i, ++p) {
		cout << *i;
	}
	cout << '"' << endl;*/
	//cout << '(';
	int pos = 0;
	for(tr1::sregex_token_iterator i(start); i != end && pos < length; ++i, ++pos) {
		//cout << "\"" << *i << "\"" << endl;
		string token(*i);
		Expression* next = NULL;
		if(token[0] == '(') {
			tr1::sregex_token_iterator newStart(++i), nextI;
			nextI = i;
			int newLength = -1;
			for(int numParens=1; i != end && pos < length && numParens > 0; ++i, ++pos, ++newLength) {
				token = *i;
				if(token[0] == '(') ++numParens;
				else if(token[0] == ')') { 
					--numParens;
					nextI = i;
				}
			}
			next = new Expression(parseTokens(newStart, newLength));
			i = nextI;
		} else if(tr1::regex_match(token, Expression::isNumber)) {
			stringstream numStr(token);
			float num;
			numStr >> num;
			next = new Number(num);
		} else if(tr1::regex_match(token, Expression::isVariable))
			next = new Variable(token);
		else if(tr1::regex_match(token, Expression::isBinaryOperator))
			next = new BinaryExpression(token);

		if(next) {
			if(prev) {
				if(BinaryExpression* bn = dynamic_cast<BinaryExpression*>(next)) {
					if(BinaryExpression* bp = dynamic_cast<BinaryExpression*>(prev)) {
						if(bn->getPrecedence() < bp->getPrecedence())
							bp->setRight(bn);
						else {
							bn->setLeft(bp);
							prev = bn;
						}
					} else {
						bn->setLeft(prev);
						prev = bn;
					}
				} else if(BinaryExpression* bp = dynamic_cast<BinaryExpression*>(prev))
					bp->setRight(next);
			} else
				prev = next;
		}
	}
	//cout << ')';
	return prev;
}
ostream& operator<<(ostream& out, Expression& e) {
	return e.printToStream(out);
}